Under the prediction model of learning, a prediction strategy is presented with an i.i.d. By exploiting the structure of F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy, improving on bounds implied by PAC-type results by a O(log n) factor. The key data structure in their result is the natural subgraph of the hypercube--the one-inclusion graph; the key step is a d VC(F) bound on one-inclunion graph density. The first main result of this s /n -1 paper is a density bound of n d-1 ( d) d, which positively resolves a conjecture of Kuzmin & Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved mistake bound for the randomized (deterministic) one-inclusion strategy for all d (for d (n)). The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization.

Under the prediction model of learning, a prediction strategy is presented with an i.i.d.

Under the prediction model of learning, a prediction strategy is presented with an i.i.d.